package leetcode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-12-25 13:34
 **/
public class LeetCode114 {

    //寻找前驱节点·
    public void flatten(TreeNode root) {
        TreeNode curr = root;
        while (curr != null) {
            //如果左子节点如果其左子节点不为空，则在其左子树中找到最右边的节点，作为前驱节点，
            // 将当前节点的右子节点赋给前驱节点的右子节点，然后将当前节点的左子节点赋给当前节点的右子节点，
            // 并将当前节点的左子节点设为空。对当前节点处理结束后，继续处理链表中的下一个节点，直到所有节点都处理结束。
            if (curr.left != null) {
                TreeNode next = curr.left;
                TreeNode predecessor = next;
                while (predecessor.right != null) {
                    predecessor = predecessor.right;
                }
                predecessor.right = curr.right;
                curr.left = null;
                curr.right = next;
            }
            curr = curr.right;
        }
    }

    //前序遍历和展开同步进行
    /*public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }
        Deque<TreeNode> stack = new LinkedList<>();
        stack.push(root);
        TreeNode pre = null;
        while (!stack.isEmpty()) {
            TreeNode curr = stack.pop();

            if (pre != null) {
                pre.left = null;
                pre.right = curr;
            }

            TreeNode left = curr.left;
            TreeNode right = curr.right;

            //右子节点先入栈
            if (right != null) {
                stack.push(right);
            }

            //左子节点入栈
            if (left != null) {
                stack.push(left);
            }

            pre = curr;
        }
    }*/


    //前序遍历
    /*public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }

        List<TreeNode> list = new ArrayList<>();
        preOrder(root, list);
        TreeNode pre = list.get(list.size() - 1);
        pre.left = null;
        pre.right = null;
        for (int i = list.size() - 2; i >= 0; --i) {
            TreeNode node = list.get(i);
            node.left = null;
            node.right = pre;
            pre = node;
        }
    }

    void preOrder(TreeNode root, List<TreeNode> list) {
        if (root == null) {
            return;
        }

        list.add(root);
        preOrder(root.left, list);
        preOrder(root.right, list);
    }*/

}
